/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
public:
  bool isPalindrome(ListNode *head){

    ListNode *p = head;
    stack<int> *s = new stack<int>();
    bool f = false;
    int length = 0;
    int cnt = 0;

    while(p){
      p = p->next;
      ++length;
    }

    p = head;
    while(p){
      if((length & 1) && (cnt == length / 2)){
        p = p->next;
        ++cnt;
        continue;
      }
      if(s->empty()){
        s->push(p->val);
      }else{
        if(s->top() == p->val){
          s->pop();
        }else{
          s->push(p->val);
        }
      }
      ++cnt;
      p = p->next;
    }
    if(s->empty()){
      f = true;
    }

    delete s;
    s = nullptr;

    return f;

  }
};